{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Difference Between Highest and Lowest of K Scores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #sorting #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #排序 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minimumDifference"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #学生分数的最小差值"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <strong>下标从 0 开始</strong> 的整数数组 <code>nums</code> ，其中 <code>nums[i]</code> 表示第 <code>i</code> 名学生的分数。另给你一个整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>从数组中选出任意 <code>k</code> 名学生的分数，使这 <code>k</code> 个分数间 <strong>最高分</strong> 和 <strong>最低分</strong> 的 <strong>差值</strong> 达到<strong> 最小化</strong> 。</p>\n",
    "\n",
    "<p>返回可能的 <strong>最小差值</strong> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [90], k = 1\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>选出 1 名学生的分数，仅有 1 种方法：\n",
    "- [<em><strong>90</strong></em>] 最高分和最低分之间的差值是 90 - 90 = 0\n",
    "可能的最小差值是 0\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [9,4,1,7], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>选出 2 名学生的分数，有 6 种方法：\n",
    "- [<em><strong>9</strong></em>,<em><strong>4</strong></em>,1,7] 最高分和最低分之间的差值是 9 - 4 = 5\n",
    "- [<em><strong>9</strong></em>,4,<em><strong>1</strong></em>,7] 最高分和最低分之间的差值是 9 - 1 = 8\n",
    "- [<em><strong>9</strong></em>,4,1,<em><strong>7</strong></em>] 最高分和最低分之间的差值是 9 - 7 = 2\n",
    "- [9,<em><strong>4</strong></em>,<em><strong>1</strong></em>,7] 最高分和最低分之间的差值是 4 - 1 = 3\n",
    "- [9,<em><strong>4</strong></em>,1,<em><strong>7</strong></em>] 最高分和最低分之间的差值是 7 - 4 = 3\n",
    "- [9,4,<em><strong>1</strong></em>,<em><strong>7</strong></em>] 最高分和最低分之间的差值是 7 - 1 = 6\n",
    "可能的最小差值是 2</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length &lt;= 1000</code></li>\n",
    "\t<li><code>0 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-difference-between-highest-and-lowest-of-k-scores](https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-difference-between-highest-and-lowest-of-k-scores](https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[90]\\n1', '[9,4,1,7]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if k >= n:\n",
    "            return nums[-1]-nums[0]\n",
    "        ans = math.inf\n",
    "        for i in range(n-k+1):\n",
    "            ans = min(ans,nums[i+k-1]-nums[i])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        \n",
    "        res = 100001\n",
    "        nums.sort()\n",
    "\n",
    "        for i in range(len(nums)-k+1):\n",
    "            res = min(res, nums[i+k-1]-nums[i])\n",
    "        \n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = float('inf')\n",
    "        for i in range(len(nums)- k + 1):\n",
    "            check = nums[i:i+k]\n",
    "            res = min(res,max(check)-min(check))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 100000\n",
    "        for i in range(k-1, len(nums)):\n",
    "            if nums[i] - nums[i-k+1] < ans:\n",
    "                ans = nums[i] - nums[i-k+1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if nums == [] or len(nums) == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        result = 99999999 #max num\n",
    "        leftPtr = 0\n",
    "        for i in range(len(nums)):\n",
    "            if i >= k - 1:\n",
    "                if result > nums[i] - nums[leftPtr]:\n",
    "                    result = nums[i] - nums[leftPtr]\n",
    "                leftPtr += 1\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums_len=len(nums)\n",
    "        nums.sort()\n",
    "        ans = float('inf')\n",
    "        for i in range(k-1,nums_len):\n",
    "            ans=min(ans,nums[i]-nums[i-k+1])\n",
    "            if ans==0:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # 开头k个数\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for right,num in enumerate(nums[k:],k):\n",
    "            ans = min(ans,num - nums[right-k+1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums = sorted(nums)\n",
    "        Min = 100001\n",
    "        for i in range(len(nums)-k+1):\n",
    "            Min = min(Min, nums[i+k-1] - nums[i])\n",
    "        return Min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        k -= 1\n",
    "        return min(nums[i+k] - nums[i] for i in range(len(nums)-k))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n==1:\n",
    "            return 0\n",
    "        res = float('inf')\n",
    "        for i in range(n-k+1):\n",
    "            res = min(res,nums[i+k-1]-nums[i])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        # 我的解法 排序+固定值滑动窗口\n",
    "        nums.sort()\n",
    "        # n = len(nums)\n",
    "        # left = 0\n",
    "        # right = left + k - 1\n",
    "        # mindic = inf\n",
    "        # while right < n:\n",
    "        #     mindic = min(mindic, nums[right]-nums[left])\n",
    "        #     left += 1\n",
    "        #     right += 1\n",
    "        # return mindic\n",
    "\n",
    "        # 代码简化\n",
    "        return min(nums[i + k -1] - nums[i] for i in range(len(nums) - k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for right, num in enumerate(nums[k:], k):\n",
    "            ans = min(ans, num-nums[right-k+1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1 or len(nums) == 1:\n",
    "            return 0\n",
    "        nums.sort(reverse = True)\n",
    "        min_res = 100000\n",
    "        for i in range(len(nums)-k+1):\n",
    "            tem = nums[i] - nums[i+k-1]\n",
    "            if tem<min_res:\n",
    "                min_res = tem\n",
    "        return min_res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        # nums=sorted(nums)\n",
    "        res=float(\"inf\")\n",
    "        for i in range(n-k+1):\n",
    "            value=nums[i+k-1]-nums[i]\n",
    "            res=min(res,value)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        \"\"\"\n",
    "        思路：\n",
    "        \"\"\"\n",
    "        sort_nums = sorted(nums)\n",
    "        if len(sort_nums) < 2:\n",
    "            return 0\n",
    "        diff_list = []\n",
    "        for i in range(len(sort_nums)):\n",
    "            if i + k - 1 < len(sort_nums):\n",
    "                diff = sort_nums[i+k-1] - sort_nums[i]\n",
    "                diff_list.append(diff)\n",
    "\n",
    "        return min(diff_list)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        n = len(nums)\n",
    "        for i in range(n - k + 1):\n",
    "            ans = min(nums[i + k - 1] - nums[i], ans)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        mins=math.inf\n",
    "        for i in range(len(nums)):\n",
    "            if i+k<=len(nums):\n",
    "                mins=min(mins,max(nums[i:i+k])-min(nums[i:i+k]))\n",
    "        return mins\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        min = 10000000\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            if nums[i+k-1] - nums[i] < min:\n",
    "                min = nums[i+k-1] - nums[i]\n",
    "        return min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for left in range(len(nums)-k+1):\n",
    "            right = left + k-1\n",
    "            ans = min(nums[right] - nums[left], ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        if n == 1:\r\n",
    "            return 0\r\n",
    "        nums.sort()\r\n",
    "        left = 0\r\n",
    "        ans = inf\r\n",
    "        while left + k - 1 < n:\r\n",
    "            ans = min(ans, nums[left + k - 1] - nums[left])\r\n",
    "            left += 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k-1] - nums[0]\n",
    "        for right, num in enumerate(nums[k:], k):\n",
    "            ans = min(ans, num-nums[right-k+1])\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums) == k:\n",
    "            return nums[-1] - nums[0]\n",
    "        mindf = float(\"inf\")\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            if nums[i + k - 1] - nums[i] < mindf:\n",
    "                mindf = nums[i + k - 1] - nums[i]\n",
    "        return mindf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        if k > 1:\n",
    "            nums = sorted(nums)\n",
    "            min_ = min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))\n",
    "            return min_\n",
    "        else:\n",
    "            return 0\n",
    "        \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        res=inf\n",
    "        if k>1:\n",
    "            for i in range(n-k+1):\n",
    "                res=min(res,nums[i+k-1]-nums[i])\n",
    "        else:\n",
    "            res=0\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i+k-1]-nums[i] for i in range(len(nums)-k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#处理序列问题的一些技巧：\n",
    "#观察排序是否影响结果，不影响就可以考虑排序能否降低复杂度\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: list[int], k: int) :\n",
    "        nums.sort()\n",
    "        ans = max(nums)\n",
    "        for right in range(k-1,len(nums)):\n",
    "            left = right - k + 1\n",
    "            ans = min(ans,nums[right] - nums[left])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        res=inf\n",
    "        if k>1:\n",
    "            for i in range(n-k+1):\n",
    "                res=min(res,nums[i+k-1]-nums[i])\n",
    "        else:\n",
    "            res=0\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if len(nums)<= k:\n",
    "            return max(nums) - min(nums)\n",
    "\n",
    "        nums.sort()\n",
    "        res = math.inf\n",
    "        left , right = 0, k-1\n",
    "        while right < len(nums):\n",
    "            res = min(nums[right] - nums[left],res) \n",
    "            left += 1\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i+k-1] - nums[i] for i in range(len(nums)-k+1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(len(nums)-k+1):\n",
    "            ans = min(ans,nums[i+k-1]-nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = nums[k - 1] - nums[0]\n",
    "        for right, num in enumerate(nums[k:], k):\n",
    "            ans = min(ans, num - nums[right - k + 1])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        # 排序  然后一个k大小的窗口滑动序列  获得最小的极差\n",
    "        nums.sort() \n",
    "        n = len(nums)\n",
    "        ans = 0x3f3f3f3f\n",
    "        for i in range(n-k+1):\n",
    "            ans = min(ans , nums[i+k-1]-nums[i])\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        min_val = 1e9\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            min_val = min(min_val, nums[i + k - 1] - nums[i])\n",
    "        return min_val\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        sorted_nums = sorted(nums)\n",
    "        min_diff = sorted_nums[len(sorted_nums) - 1]\n",
    "        for index, num in enumerate(sorted_nums):\n",
    "            if index + k <= len(sorted_nums):\n",
    "                diff = sorted_nums[index + k - 1] - sorted_nums[index]\n",
    "                min_diff = diff if min_diff > diff else min_diff\n",
    "\n",
    "        return min_diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        l = 0\n",
    "        M = nums[l+k-1] - nums[l]\n",
    "        for i in range(len(nums)-k+1):\n",
    "            l = i\n",
    "            M = min(M, nums[l+k-1] - nums[l])\n",
    "        return M\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if k > n:\n",
    "            return max(nums) - min(nums)\n",
    "\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        l = 0\n",
    "        r = l + k\n",
    "        while r <= n:\n",
    "            window = nums[l:r]\n",
    "            ans = min(ans, max(window) - min(window))\n",
    "            l, r = l + 1, r + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\r\n",
    "        n = len(nums)\r\n",
    "        nums.sort()\r\n",
    "        left = 0\r\n",
    "        ans = inf\r\n",
    "        while left + k - 1 < n:\r\n",
    "            ans = min(ans, nums[left + k - 1] - nums[left])\r\n",
    "            left += 1\r\n",
    "        return ans\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n=len(nums)\n",
    "        # nums=sorted(nums)\n",
    "        res=float(\"inf\")\n",
    "        for i in range(n-k+1):\n",
    "            value=nums[i+k-1]-nums[i]\n",
    "            res=min(res,value)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MAX = 100000\n",
    "    def insertSort(self,nums:List[int]):\n",
    "        for i in range(1,len(nums)):\n",
    "            tmp = nums[i]\n",
    "            j = i-1\n",
    "            while j >= 0:\n",
    "                if nums[j] > tmp: nums[j+1] = nums[j]\n",
    "                else: break\n",
    "                j-=1\n",
    "            nums[j+1] = tmp\n",
    "\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        self.insertSort(nums)\n",
    "        l = 0;r = k-1\n",
    "        df_min = Solution.MAX\n",
    "        while r < len(nums):\n",
    "            tmp = nums[r] - nums[l]\n",
    "            df_min = df_min if df_min < tmp else tmp\n",
    "            r+=1;l+=1\n",
    "        return df_min\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        i=0\n",
    "        res=nums[-1]-nums[0]\n",
    "        while i<len(nums)-k+1:\n",
    "            res=min(res,nums[i+k-1]-nums[i])\n",
    "            i+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        if len(nums)==1:\n",
    "            return 0\n",
    "        ans=99999999\n",
    "        for i in range(len(nums)-k+1):\n",
    "            ans=min(ans,nums[i+k-1]-nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(j-i for i, j in zip(nums, nums[k-1:]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = inf\n",
    "        i = 0\n",
    "        n = len(nums)\n",
    "        while i+k<=n:\n",
    "            ans = min(ans,nums[i+k-1]-nums[i])\n",
    "            i+=1\n",
    "            \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        ans = 100000\n",
    "        nums.sort(reverse=True)\n",
    "        i = 0\n",
    "        while i + k <= len(nums):\n",
    "            ans = min(ans, nums[i] - nums[i + k - 1])\n",
    "            i += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k==1:\n",
    "            return 0\n",
    "        lt=len(nums)\n",
    "        nums.sort()\n",
    "        ans=[]\n",
    "        flag=nums[-1]-nums[0]\n",
    "        for i in range(k-1,lt):\n",
    "            tflag=nums[i]-nums[i-k+1]\n",
    "            if tflag < flag:\n",
    "                flag = tflag\n",
    "        return flag\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        gap = []\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            for i in range(len(nums)-k+1):\n",
    "                gap.append(nums[i+k-1] - nums[i])\n",
    "\n",
    "            gap.sort()\n",
    "            return gap[0]\n",
    "\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()   #首先对数组进行排序，从小到大排序\n",
    "        ans=nums[k-1]-nums[0]  #初始化第一个滑窗为nums[:k],初始化答案变量为滑窗里面最大值和最小值的差值\n",
    "        for right,num in enumerate(nums[k:],k):  #窗口右边界为right,左边界为left\n",
    "            left=right-k+1\n",
    "            ans=min(ans,num-nums[left])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        diff = float('inf')\n",
    "        n = len(nums)\n",
    "        if k == 0 or len(nums) == 1:\n",
    "            return 0\n",
    "        for i in range(n-k+1):\n",
    "            diff = min(diff, nums[i+k-1]-nums[i])\n",
    "        return diff\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        a = float('inf')\n",
    "        for i in range(len(nums)-k+1):\n",
    "            a=min(a,nums[i+k-1]-nums[i])\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        return min(nums[i + k - 1] - nums[i] for i in range(len(nums) - k + 1))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "\n",
    "        if not nums:\n",
    "            return 0\n",
    "        if k > n:\n",
    "            return max(nums) - min(nums)\n",
    "\n",
    "        nums.sort()  # O(nlogn)\n",
    "        ans = inf\n",
    "        l = 0\n",
    "        r = l + k\n",
    "        while r <= n:  # O(n)\n",
    "            ans = min(ans, nums[r - 1] - nums[l])\n",
    "            l, r = l + 1, r + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return 0\n",
    "        \n",
    "        nums.sort(reverse=True)\n",
    "\n",
    "        result = nums[0] +1\n",
    "        \n",
    "        pos = 0\n",
    "        while pos + k <= len(nums):\n",
    "            result = min(result, nums[pos] - nums[pos+k -1])\n",
    "            pos += 1\n",
    "        \n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def InsertionSort(self,a):\n",
    "        n = len(a)\n",
    "        for i in range(1,n):\n",
    "            x = a[i]\n",
    "            j = i - 1\n",
    "            while j >= 0:\n",
    "                if x > a[j]:\n",
    "                    a[j+1] = a[j]\n",
    "                    j -= 1\n",
    "                else:\n",
    "                    break\n",
    "            a[j+1] = x\n",
    "\n",
    "\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        # self.InsertionSort(nums)\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        ret = 100000\n",
    "        for i in range(n-k+1):\n",
    "            ans = nums[i+k-1] - nums[i]\n",
    "            if ans < ret:\n",
    "                ret = ans\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        n = len(nums)\n",
    "        if n==1 or k==1 or k>n:\n",
    "            return 0\n",
    "        a,b=0, k-1\n",
    "        nums.sort()\n",
    "        mi = 10000000\n",
    "        while b < n:\n",
    "            mi = min(mi, nums[b] - nums[a])\n",
    "            a += 1\n",
    "            b += 1\n",
    "        return mi\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        if k == 1:\n",
    "            return 0\n",
    "        nums.sort()\n",
    "        min_val = float('inf')\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            cur = nums[i + k - 1] - nums[i]\n",
    "            if cur < min_val:\n",
    "                min_val = cur\n",
    "        return min_val\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        n = len(nums)\n",
    "        if n <2:\n",
    "            return 0\n",
    "        ans = inf\n",
    "        for right in range(n-k+1):\n",
    "            ans = min(ans, nums[right + k-1] - nums[right])\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        res = inf\n",
    "\n",
    "        for right, x in enumerate(nums[k-1:], k-1):\n",
    "            left = right-k+1\n",
    "            res = min(res, x-nums[left])\n",
    "\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        res = inf\n",
    "        nums.sort()\n",
    "        for i in range(k - 1, len(nums)):\n",
    "            res = min(res, nums[i] - nums[i - k + 1]) \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "\n",
    "        nums.sort()\n",
    "        # left=0\n",
    "        # right=k-1\n",
    "        n=len(nums)\n",
    "        ans=float(\"inf\")\n",
    "        # i的取值范围就在 i,到 i+k-1的范围。从 i 开始连续 k个数\n",
    "        for i in range(n-k+1):\n",
    "            diff=nums[i+k-1]-nums[i]\n",
    "            ans=min(ans,diff)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        ans = 100000\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            ans = min(ans, nums[i + k - 1] - nums[i])\n",
    "            if not ans: return ans\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        res = inf\n",
    "        for i in range(len(nums) - k + 1):\n",
    "            # print(i + k, i)\n",
    "            res = min(res, nums[i + k - 1] - nums[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort(reverse = True)\n",
    "        n = len(nums)\n",
    "        res = float('inf')\n",
    "        for i in range(n-k+1):\n",
    "            res = min(res, nums[i]-nums[i+k-1])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import inf\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        ans = inf\n",
    "        #right=k -1\n",
    "        nums.sort()\n",
    "        if k ==1  or len(nums) == 0:\n",
    "            return 0\n",
    "        for right in range(k-1,len(nums)):\n",
    "            ans = min(ans,nums[right] -nums[left])\n",
    "            left  +=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "\n",
    "        nums_len = len(nums)\n",
    "        date_list = []\n",
    "        date_min = 999999\n",
    "        for i in range(0, nums_len - k + 1):\n",
    "            date_list = nums[i:i + k:]\n",
    "            date_min = min(date_min, date_list[-1] - date_list[0])\n",
    "\n",
    "\n",
    "        return date_min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        return min(s[i + k - 1] - s[i] for i in range(len(s) - k + 1)) if k > 1 and (s := sorted(nums)) else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        k -= 1\n",
    "        fh = float('inf')\n",
    "        for i in range(len(nums)-k):\n",
    "            fh = min(fh, nums[i+k]-nums[i])\n",
    "        return fh\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minimumDifference(self, nums: List[int], k: int) -> int:\n",
    "        nums.sort()\n",
    "        # min_value=float('inf')\n",
    "        # for i in range(k-1,len(nums)):\n",
    "        #     min_value = min(max(nums[i-k+1:i+1])-min(nums[i-k+1:i+1]), min_value)\n",
    "\n",
    "        # return min_value\n",
    "        return min([nums[i]-nums[i-k+1] for i in range(k-1,len(nums))])"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
